<!DOCTYPE html>
<html>
  <head>
    <meta charset="utf-8"> <meta name="viewport" content="width=device-width">
    <title>集合覆盖问题的几种近似算法</title>
    <meta name="viewport" content="width=device-width,initial-scale=1, shrink-to-fit=no">
    <!-- Bootstrap CSS -->
    <link rel="stylesheet"
          href="https://cdn.jsdelivr.net/npm/bootstrap@4.5.0/dist/css/bootstrap.min.css"
          integrity="sha384-9aIt2nRpC12Uk9gS9baDl411NQApFmC26EwAOH8WgZl5MYYxFfc+NcPb1dKGj7Sk"
          crossorigin="anonymous">
    <link rel="stylesheet"
          href="//cdnjs.cloudflare.com/ajax/libs/highlight.js/10.5.0/styles/androidstudio.min.css">
<!--    <link rel="stylesheet" href="/web_template_css.css">-->
    <!-- this is highlight.js -->
    <script src="https://polyfill.io/v3/polyfill.min.js?features=es6"></script>
    <script id="MathJax-script" async
            src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js">
    </script>
    <script  src="https://cdn.jsdelivr.net/npm/jquery@3.5.1/dist/jquery.slim.min.js"
    integrity="sha384-DfXdz2htPH0lsSSs5nCTpuj/zy4C+OGpamoFVy38MVBnE+IbbVYUew+OrCXaRkfj" crossorigin="anonymous"></script>
    <script src="https://cdn.jsdelivr.net/npm/popper.js@1.16.0/dist/umd/popper.min.js"
    integrity="sha384-Q6E9RHvbIyZFJoft+2mJbHaEWldlvI9IOYy5n3zV9zzTtmI3UksdQRVvoxMfooAo" crossorigin="anonymous"></script>
    <script src="https://cdn.jsdelivr.net/npm/bootstrap@4.5.0/dist/js/bootstrap.min.js"
    integrity="sha384-OgVRvuATP1z7JjHLkuOU7Xw704+h835Lr+6QL9UvYjZE3Ipu6Tp75j7Bh/kR0JKI" crossorigin="anonymous"></script>
    <script src="//cdnjs.cloudflare.com/ajax/libs/highlight.js/10.5.0/highlight.min.js"></script>
    <style>
      img{
        display: block;
        height: auto;
        max-width: 100%;
      }
    </style>
  </head>
  <body>
    <nav class="navbar navbar-expand-lg navbar-light bg-light">
        <a class="navbar-brand" href="#">kvrmnks</a>
        <button class="navbar-toggler" type="button" data-toggle="collapse" data-target="#navbarNav" aria-controls="navbarNav" aria-expanded="false" aria-label="Toggle navigation">
          <span class="navbar-toggler-icon"></span>
        </button>
        <div class="collapse navbar-collapse" id="navbarNav">
          <ul class="navbar-nav">
            <li class="nav-item active">
              <a class="nav-link" href="./../../../../../index.html" target="_self">Home <span class="sr-only">(current)</span></a>
            </li>
            <li class="nav-item">
              <a class="nav-link" href="./../../../../../blog.html">Blog</a>
            </li>
            <li class="nav-item">
              <a class="nav-link" href="./../../../../../about.html">About</a>
            </li>
          </ul>
        </div>
      </nav>



    <div class='container'>
      <h1>集合覆盖问题的几种近似算法</h1>

<h2>问题简介</h2>

<p>给定一个有限非空集合\(A\), 定义集合(集群)\(S, s.t.\forall x\in S, s \subset A\), 求解一个指标集\(I\), 满足\(\bigcup _{i=1}^{|I|}S_{i} = A\)</p>

<p>使得\(|I|\)最小.</p>

<h2>基于线性规划的集合最小覆盖的近似算法</h2>

<p>首先花30s将这个问题转化成线性规划的形式.</p>

<p>另外既然都用线性规划了, 不妨再给集群\(S\)的每个元素加个权值函数.</p>

<p>不妨令\(|A| = n, |S| = m\), 假设\(m\)个变量, 对于\(x_{i}\)表示集群中的第\(i\)个集合选或者不选.</p>

<p>于是\(x \in \{0,1\}\)</p>

<p>定义权函数\(W: x \rightarrow R, x\in S\) .</p>

<p>于是最小化函数为\(\sum W(x_{i})x_{i}\)</p>

<p>首先朴素的约束, \(x_{i} \in \{0,1\}\)</p>

<p>对于集合\(A\)第\(j\)个元素, \(\sum x_{i} \geq 1 , A_{j} \in S_{i}\)</p>

<p>按照线性规划设计近似算法的理论, 首先把上述整数规划问题转化为线性规划.</p>

<p>说了这么多, 其实就是把变量的定义域换成\([0, \infty]\).</p>

<p>为了方便之后的分析, 假设\(k = \max(|S_{i}|,S_{i} \in S)\)</p>

<p>如果\(x_{i} \geq \frac{1}{k}\), 则代表选择这个集合, 根据反证法, 这样得到的一定是一个可行解, 证明比较简答, 这里就不说了.</p>

<p>下面进行近似上界的分析.</p>

<p>依旧是依托这个不等式\(x_{i} \geq \frac{1}{k}\), 对每个集合\(i\)求和得到并且\(k\sum w_{i}x_{i} \geq \sum w_{i}\)</p>

<p>于是得到近似上界为\(k\)</p>

<h2>基于组合方法的集合覆盖算法</h2>

<p>依旧是很朴素的贪心方法, 即每次选取最多的能够多覆盖的集合.</p>

<p>为了描述方便, 定义\(Set_{i,j}\)表示第\(i\)次贪心之后的\(S_{j}\).</p>

<p>每次贪心, 找到\(S\)中最大的元素, 维护一个已经被覆盖的元素集合\(Cov\), 将找到的最大的集合中的元素并入\(Cov\)中, 并把这些元素从\(S\)中剔除出去.</p>

<h3>引理</h3>

<p>假设上述算法进行了\(t\)次, 则对于任意一种覆盖方式\(C\).</p>

<p>设集类\(S\)中最大的元素大小为\(k\)</p>

<p>满足\[t \leq \sum_{s\in C}\sum_{i=1}^{|s|}\frac{1}{i}\]</p>

<p>应用归纳法进行证明.</p>

<p>首先当\(k=1\)时, 显然等号成立.</p>

<p>不妨假设\(k=p-1\)时成立.</p>

<p>当\(k=p\)时, 考虑整个贪心过程中, 选择集合的大小是单调不增的, 也就是存在一个边界值\(\hat{t}\), 使得在\(\hat{t}\)时刻之后选择的集合的大小都小于\(p\)</p>

<p>根据归纳假设得到\(t-\hat{t} \leq \sum_{\hat{c}}\sum_{i=1}^{|s_{\hat{t},j}|}\frac{1}{i}\)</p>

<p>考虑时刻\(1-\hat{t}\)时, 考虑对这一部分进行一个估价, 因为在前\(\hat{t}\)次中, 每次取走的元素个数一定是大于等于\(k\)的, </p>

<p>于是有不等式\(\hat{t} \leq \frac{Cov_{\hat{t}}}{k}\)</p>

<p>考虑对\(Cov_{\hat{t}}\)的大小进行估计, 显然(并不显然)\(|Cov_{i}| \leq \sum |Set[0][i] - Set[\hat{t}][i]|\)</p>

<p>稍微展开一下\(|Cov_{i}| \leq \sum_{i \in M_{1}}\sum_{Set[\hat{t}][i]+1}^{Set[0][i]}\)</p>

<p>于是有\(Cov_{i} \leq \sum_{i \in \hat{c}}\sum_{Set[\hat{t}][i]+1}^{Set[0][i]}\)</p>

<p>注意这里\(M_{1} 与 M_{2}\)是**近乎等价**的</p>

<p>\[\hat{t} \leq \sum_{i \in \hat{c}}\sum_{Set[\hat{t}][i]+1}^{Set[0][i]}\frac{1}{k} \leq \sum_{i \in \hat{c}}\sum_{Set[\hat{t}][i]+1}^{Set[0][i]}\frac{1}{j}\]</p>

<p>于是\[t \leq \sum_{i \in \hat{C}} \sum_{1}^{Set[0][i]}\frac{1}{j}\]</p>

<p>于是近似上界\(ln(k)\)</p>

<h2>基于原始对偶方法的集合最小覆盖的近似算法</h2>

<p>首先沿用上面的整数规划转换成线性规划的步骤, 即.</p>

<p>最小化\(\sum w_{i}x_{i}\)</p>

<p>约束条件为\(\sum_{e_{j} \in x_{i}}x_{i} \geq 1\)</p>

<p>\(x_{i}\geq 0\)</p>

<p>原始对偶方法是指首先将松弛后的线性规划方法进行对偶, 取其对偶问题, 通过对对偶问题进行进一步的分析.</p>

<p>注意这里的进一步分析是指不一定要通过运筹学的一些固有方式, 包括组合技术的一些方式也是可以使用的.</p>

<p>由于对偶问题的固有性质, 对偶问题的一个可行解天然就成了最优解的一个界.</p>

<p>转对偶问题得到</p>

<p>最大化\(\sum{y_i}\)</p>

<p>约束条件为\(\sum_{e_{j} \in x_{i}}y_{j} \leq w_{i}\)</p>

<p>\(y_{i} \geq 0\)</p>

<p>这里采用的依旧是组合技术来优化对偶问题.</p>

<p>由对偶问题的性质可以知道我们要尽可能的使得和尽量大来逼近最优值.</p>

<p>这里通过以下方式逐步优化对偶问题的解.</p>

<p>初始情况下\(y_{i} = 0\)</p>

<p>这显然是对偶问题的一个可行解, 但是不一定是原问题的一个可行解.</p>

<p>按照某个顺序枚举集合中的元素, 动态维护集群中选了哪些集合.</p>

<p>若某个元素\(e_{i}\)这个时候没有被覆盖, 我们想办法提高\(y_{i}\)的值, 知道某个约束条件被严格满足.</p>

<p>显然这样做之后依旧是一个可行解, 且想法十分的单纯, 当找到那个约束被严格满足的集合, 加入动态维护的集合中去.</p>

<p>这样一路贪心下来就得到了一个集群\(I\), 表示哪些集合被选取了, 且由贪心过程一定覆盖了\(A\)</p>

<p>下面开始分析这个做法的近似度.</p>

<p>\(\sum_{i\in I} w_{i} = \sum_{i \in I} \sum_{e_{j} \in i}y_{j}\)</p>

<p>假设集群中元素最大为\(k\)</p>

<p>上式放缩得到</p>

<p>\(\sum_{i \in I}\sum_{e_{j} \in i} y_{i} \leq k\sum{y_i} \leq k*OPT\)</p>

<p>于是近似度为\(k\)</p>


    </div>
    <script>
      hljs.initHighlightingOnLoad()
    </script>
  <script src="https://cdnjs.cloudflare.com/ajax/libs/highlightjs-line-numbers.js/2.5.0/highlightjs-line-numbers.min.js"></script>
  <script>
      hljs.initHighlightingOnLoad();
      hljs.initLineNumbersOnLoad();
  </script>
  </body>
</html>